import java.util.*;

public class Test {

    //前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        //1. 统计每个单词出现的次数
        for(String word : words){
            if(!map.containsKey(word)){
                map.put(word,1);
            } else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }

        //2. 建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
             public int compare (Map.Entry<String,Integer> o1,Map.Entry<String,Integer>o2){
                 if(o1.getValue().compareTo(o2.getValue()) == 0){
                     return o2.getKey().compareTo(o1.getKey());
                 }
                 return o1.getValue().compareTo(o2.getValue());
             }
        });

        //3.遍历map
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            if(minHeap.size() < k){
                minHeap.offer(entry);
            } else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if(top.getValue().compareTo(entry.getValue()) == 0) {
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }

        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {
        /*
        HashMap<Student,Integer> map2 = new HashMap<>();
        map2.put(new Student(),10);
        map2.put(new Student(),20);
        */

        //去重
//        int[] array = {1,1,2,3,4,5,7,8,3,1,12,4,5,7,43,3,3,5};
//        HashSet<Integer> set = new HashSet<>();
//        for (int i = 0; i < array.length; i++) {
//            set.add(array[i]);
//        }
//        System.out.println(set);


        //找到这组数据当中 第一个重复的数据
        int[] array = {1,1,2,3,4,5,7,8,3,1,12,4,5,7,43,3,3,5};
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.contains(array[i])) {
                set.add(array[i]);
            }else {
                System.out.println(array[i]);
                return;
            }
        }

        //统计 一篇 英文阅读中 每个单词 出现的次数
        //HashMap   参数：String[]
        String[] string = {"and","is","are"};
        HashMap<String,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < string.length; i++) {
            String s = string[i];
            if(hashMap.containsKey(s)){
                Integer count = hashMap.get(s);
                hashMap.put(s,++count);
            } else{
                hashMap.put(s,1);
            }
        }


    }


    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        for(int i = 0;i < jewels.length(); i++){
            char ch = jewels.charAt(i);
            set.add(ch);
        }
        int count = 0;
        for(int i = 0;i < stones.length(); i++){
            char ch = stones.charAt(i);
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    //存在重复元素
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}
